<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>Title</title>
</head>
<body>

</body>
<script>
	// 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
	/**
	 * 检测链表中是否存在环，并返回环的起始节点。
	 * 使用快慢指针算法（Floyd's Cycle Detection）：
	 *  1. 快指针每次移动两步，慢指针每次移动一步，直到相遇或到达链表末端
	 *  2. 若相遇，将其中一个指针重置到链表头，然后两个指针同步移动，再次相遇点即为环起点
	 *
	 * @param {ListNode} head - 链表头节点
	 * @returns {ListNode|null} 环的起始节点，若无环则返回null
	 */
	function detectCycle(head){
		// 空链表或单节点链表直接返回null
		if (!head || !head.next) return null
		
		let slow = head
		let fast = head
		
		// 第一阶段：检测环是否存在
		while(fast && fast.next){
			slow = slow.next
			fast = fast.next.next
			// 快慢指针相遇说明存在环
			if(slow === fast) break
		}
		
		// 循环终止条件：到达链表末端（无环）
		if (fast === null || fast?.next === null) return null
		
		// 第二阶段：定位环的起始节点
		fast = head  // 重置快指针到链表头
		while (slow !== fast){
			slow = slow?.next
			fast = fast?.next
		}
		return slow  // 相遇点即为环起点
	}

	{
		const node1 = {val: 1};
		const node2 = {val: 2};
		node1.next = node2;
		console.log(detectCycle(node1)); // 预期输出: null
		
	}
	{
		const node1 = {val: 1};
		node1.next = node1;
		console.log(detectCycle(node1) === node1); // 预期输出: true
		
	}
	{
		const node1 = {val: 1};
		const node2 = {val: 2};
		node1.next = node2;
		node2.next = node1; // 形成环
		console.log(detectCycle(node1) === node1); // 预期输出: true
		
	}
	{
		const nodes = Array.from({length: 5}, (_, i) => ({val: i+1}));
		nodes[0].next = nodes[1];
		nodes[1].next = nodes[2];
		nodes[2].next = nodes[3];
		nodes[3].next = nodes[4];
		nodes[4].next = nodes[2]; // 环入口在nodes[2]
		console.log(detectCycle(nodes[0]) === nodes[2]); // 预期输出: true
		
	}
	{
		const node1 = {val: 1};
		const node2 = {val: 2};
		node1.next = node2;
		node2.next = node2; // 尾节点自环
		console.log(detectCycle(node1) === node2); // 预期输出: true
		
	}
	{
		const nodes = Array.from({length: 10}, (_, i) => ({val: i+1}));
		nodes.forEach((n, i) => n.next = nodes[i+1] || nodes[5]); // 第5个节点是入口
		console.log(detectCycle(nodes[0]) === nodes[5]); // 预期输出: true
		
	}
	{
		console.log(detectCycle(null)); // null
		console.log(detectCycle({val:1})); // null
	}
</script>
</html>